import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCases = Integer.parseInt(br.readLine().trim());
		int i = 1;
		while(testCases-- != 0) {
			String str = br.readLine();
			
			
			StringBuffer sb = new StringBuffer();
			int index = 0;
			while(str.charAt(index) != ' ') {
				sb.append(str.charAt(index++));
			}
			int m = Integer.parseInt(sb.toString());
			index++;
			
			sb = new StringBuffer();
			while(index < str.length() && str.charAt(index) != ' ') {
				sb.append(str.charAt(index++));
			}
			int n = Integer.parseInt(sb.toString());
			index++;
			
			sb = new StringBuffer();
			while(index < str.length()) {
				sb.append(str.charAt(index++));
			}
			
			String msg = sb.toString();
			System.out.println(i++ + " " + encodeMsg(m, n, encodeMsg(msg)));
		}
	}
	
//	public static void main(String[] args) throws Exception {
//		System.out.println(encodeMsg("ACM"));
//	}
	
	
	private static String encodeMsg(int m, int n, String encodedMsg) {
		int[][] mat = new int[m][n];
		int index = 0;
		int upperx = 0, uppery = 0;
		int lowerx = m - 1, lowery = n - 1;
		while(lowerx >= upperx && lowery >= uppery && index < encodedMsg.length()) {
			for(int j = uppery; j <= lowery && index < encodedMsg.length(); j++) {
				if(encodedMsg.charAt(index++) == '1') {
					mat[upperx][j] = 1;
				} else {
					mat[upperx][j] = 0;
				}
			}
			
			for(int i = upperx + 1; i <= lowerx && index < encodedMsg.length(); i++) {
				if(encodedMsg.charAt(index++) == '1') {
					mat[i][lowery] = 1;
				} else {
					mat[i][lowery] = 0;
				}
			}
			
			for(int j = lowery - 1; j >= uppery && lowerx > upperx && index < encodedMsg.length(); j--) {
				if(encodedMsg.charAt(index++) == '1') {
					mat[lowerx][j] = 1;
				} else {
					mat[lowerx][j] = 0;
				}
			}
			
			for(int i = lowerx - 1; i > upperx && lowery > uppery && index < encodedMsg.length(); i--) {
				if(encodedMsg.charAt(index++) == '1') {
					mat[i][uppery] = 1;
				} else {
					mat[i][uppery] = 0;
				}
			}
			
			upperx++;
			uppery++;
			lowerx--;
			lowery--;
		}
		
		StringBuffer sb = new StringBuffer();
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < n; j++) {
				sb.append(mat[i][j]);
			}
		}
		return sb.toString();
	}
	
	private static String encodeMsg(String msg) {
		StringBuffer enc = new StringBuffer();
		for(int i = 0; i < msg.length(); i++) {
			enc.append(encodeMsg(msg.charAt(i)));
		}
		return enc.toString();
	}
	
	private static String encodeMsg(char c) {
		int value = getValue(c);
		String enc = "";
		for(int i = 0; i < 5; i++) {
			if((value & (1 << i)) != 0) {
				enc = "1" + enc;
			} else {
				enc = "0" + enc;
			}
		}
		return enc.toString();
	}
	
	private static int getValue(char c) {
		if(c == ' ') {
			return 0;
		}
		
		return c - 'A' + 1;
	}

}
